//https://leetcode.cn/problems/decode-ways/

class Solution {
public:
    int numDecodings(string s) {
        //1.创建dp表
        //2.初始化
        //3.填值
        //4.返回值
        int n = s.size();

        vector<int> dp(n);

        if (s[0] != '0') dp[0] += 1;
        if (n == 1) return dp[0];
        if (s[0] != '0' && s[1] != '0') dp[1]++;
        int t = 10 * (s[0] - '0') + (s[1] - '0');
        if (10 <= t && t <= 26) dp[1]++;

        for (int i = 2; i < n; i++)
        {
            if (s[i] != '0') dp[i] += dp[i - 1];
            int t = 10 * (s[i - 1] - '0') + (s[i] - '0');
            if (10 <= t && t <= 26) dp[i] += dp[i - 2];
        }

        return dp[n - 1];

    }
};

//优化版本
class Solution {
public:
    int numDecodings(string s) {
        //1.创建dp表
        //2.初始化
        //3.填值
        //4.返回值
        int n = s.size();

        vector<int> dp(n + 1);

        if (s[1 - 1] != '0') dp[1] += 1;
        if (n == 1) return dp[1];

        //虚拟节点的初始化
        dp[0] = 1;

        for (int i = 2; i <= n; i++)
        {
            if (s[i - 1] != '0') dp[i] += dp[i - 1];
            int t = 10 * (s[i - 1 - 1] - '0') + (s[i - 1] - '0');
            if (10 <= t && t <= 26) dp[i] += dp[i - 2];
        }

        return dp[n];

    }
};